/*
209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/?envType=problem-list-v2&envId=binary-search
难度：中等
李佳韵 2024/08/29
二分查找

*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        // sum 表示当前子数组的和
        int sum = nums[0];
        // left 和 right 分别表示滑动窗口的左右边界
        int left = 0, right = 0;
        // count 用于记录满足条件的最小子数组长度
        int count = n;
        // find 用于标记是否找到满足条件的子数组
        bool find = false;
        while (left < n) {
            // 尝试扩大窗口，直到子数组和大于等于目标值
            while (right < n && sum < target) {
                right++;
                if (right < n)
                    sum += nums[right];
            }
            // 如果找到了满足条件的子数组
            if (sum >= target) {
                find = true;
                // t 表示当前子数组的长度
                int t = right - left + 1;
                // 更新最小子数组长度
                count = min(count, t);
                // 缩小窗口左侧边界，继续寻找更短的子数组
                sum -= nums[left];
                left++;
            } else {
                // 如果无法再找到满足条件的子数组，退出循环
                break;
            }
        }
        // 如果找到满足条件的子数组，返回最小长度；否则返回 0
        return find? count : 0;
    }
};

int main() {
    cout << "请输入目标值：";
    int target;
    cin >> target;
    cout << "请输入数组元素个数：";
    int n;
    cin >> n;
    vector<int> nums;
    cout << "请输入数组元素：";
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        nums.push_back(num);
    }
    Solution solution;
    int result = solution.minSubArrayLen(target, nums);
    if (result > 0) {
        cout << "满足和大于等于目标值的最小子数组长度为：" << result << endl;
    } else {
        cout << "不存在满足条件的子数组。" << endl;
    }
    return 0;
}